\documentclass[12pt,a4paper]{article}

\usepackage[margin = 1.5cm]{geometry}
\usepackage{CJK}
\usepackage{graphicx}
\usepackage{indentfirst}

\setlength{\parindent}{2em}

\begin{CJK}{UTF8}{fzst}
  \title{编程中常见的临界情况变量值设置的问题}
  \author{陈如山\\chenrs@ics.neu.edu.cn}
  \date{2008年 07月 09日}
\end{CJK}

\begin{document}
\begin{CJK}{UTF8}{fzst}
  \maketitle

  编程中经常会遇到临界情况设置变量值的问题，比如循环开始时一些变量的值设成什么才好，之前我一直搞不太懂，今天发现一招，下面举例子说明。

  比如我现在要编一个对链表进行快排的算法，快排中有一个 Partition 的问题，Partition 中有一个循环用于分开小于和大于 Pivot 的元素，中间过程大体是这样的：
  
  \begin{figure}[h]
    \centering
    \includegraphics[scale = 0.8, viewport = 8 340 600 500, clip]{list.pdf}
    \caption{链表快排 Partition 中间过程}
  \end{figure}

  大家都知道快排中间过程会出现如图所示的样子，那开始时 pSmall, pLarge 都应该怎么设呢？中间过程如果 pSmall == NULL 而 pLarge != NULL 又怎么办？其实这都不用想，你只要针对这个一般情况进行讨论就行了，最后你就很自然的解决了这里会遇到的很多临界问题。

  针对这个一般情况，由于我们循环每次都是对 pNow 进行处理，所以很自然想到
  \begin{quote}
    \begin{itemize}
    \item {\bf pNow $<$ pPivot 怎么处理}
    \item {\bf pNow $>=$ pPivot 怎么处理}
    \end{itemize}
  \end{quote}
  
  然后思路就很自然的延伸到怎么分别对这两个情况进行处理：
  \begin{enumerate}
  \item {\bf pNow $<$ pPivot 的情况}

    做法其实很简单：就是把现在 pNow 指向的结点加入到小于 pivot 的队列中。

    由于小于 pivot 的队列最后一个结点由 pSmall 指着，一想到这儿，很自然的又要分情况了：
    \begin{itemize}
    \item {\bf pSmall == NULL 怎么处理}
    \item {\bf pSmall != NULL 怎么处理}
    \end{itemize}

    然后我们就分别开始处理这两种情况：
    \begin{enumerate}
    \item {\bf pSmall == NULL 的情况}

      做法：交换 pPivot--$>$next 和 pNow
      
    \item {\bf pSmall != NULL 的情况}

      做法：交换 pSmall--$>$next 和 pNow
    \end{enumerate}
    
  \item {\bf pNow $>=$ pPivot 的情况}

    做法：很简单，直接把 pLarge 指针前移就完了。
    
  \end{enumerate}

  这样整个循环的框架大体就是：
  
  \vspace{2em}
  \fbox{
    \parbox{13cm}{
      while () \{\\
      \hspace*{8ex}if (pNow $<$ pPivot) \{\\
      \hspace*{16ex}if (pSmall == NULL) \{\\
      \hspace*{24ex}...\\
      \hspace*{16ex}\} else \{\\
      \hspace*{24ex}...\\
      \hspace*{16ex}\}\\
      \hspace*{8ex}\} else \{\\
      \hspace*{16ex}...\\
      \hspace*{8ex}\}\\
      \}\\
    }
  }\\[2ex]

  所以像这样的问题，很多时候不用刻意单独去考虑临界问题，这种问题是你从一般情况出发考虑必然会经过的一关，是一个顺其自然的过程。所以这种问题只要从一般情况开始考虑就好了。
\end{CJK}
\end{document}
